1 Quantum Computers

At page 51 of Scientific November 2002 is written: "How many computational steps are needed to find the prime factors of a 300-digit number? The best classical algorithm would take about 5*10E24 steps. By taking advantage of innumerable quantum states a quantum factoring algorithm would take only 5*10E10 steps"
My question is why are both not the same. How do we explain that a quantum computer requires such a relative small number of steps.

Suppose this the best classical algorithm:

1 INPUT 300dn (300-digit number)
2 N1 = 1
3 DO
4   N1 = N1 + 1
5   N2 = 300dn/N1
6   Is N1 * Int(N2) = 300dn
7   Yes Is N2 prime ?
8   Yes Print "Eureka" N1, N2 : Exit
9   No Exit
10 Loop Until N1 > SQR(300dn)
11 Print 300dn "is prime number !"

Line 7: This test is a small program (inner loop) of rougly 6 lines which is almost identical as the above program.

Line 10 Can also be written as: 10 Loop Until N1 * N1 > 300dn This involves a multiplication of two 150-digit numbers

Line 10 is important because it answers the question: How many times do we have to excute the outer loop: Answer: 10E150 times

Roughly speaking each loop consists of 10 steps. That means the total number of steps is 10E151.

The first improvement is to replace line 4 by: 4 N1 = N1 + 2 i.e. test only odd numbers. The problem is both that the classical computer and the quantum computer will benefit from this improvement which does not explain the difference between the two.

One possibility is to perform many loops in parallel, but that means more hardware. On the otherhand this is not a true solution because it can be done for both a classical computer and a quantum computer.

The article in Scientific American gives the answer: "By taking advantage of innumerable quantum states" But how do you do that in practice in order to reduce the number of steps (outer loops ?) of the quantum computer?

Nick

[Moderator's note: "Shor's algorithm" is the answer to your question. More generally, quantum computers can be more efficient than classical computers because a superposition of states can "perform many loops in parallel" without requiring more hardware (roughly speaking).

-- KS]

2 Quantum Computers

wrote:

>	Suppose this the best classical algorithm:

It isn't.

Anyway, practical quantum copmputers can now factor numbers up to 15 in, err, milliseconds. I guess the next milestone will be when one runs Microsoft Office.

Charles

3 Quantum Computers

>	(roughly speaking). - KS]

Willfully disregarding the disclaimer, is there really any sense in which this is true? It's oft-stated, but from what I know of Shor's algorithm (and what I know is fairly minimal), it works because quantum computers can do FFTs very quickly. If one were really able to do as many loops in parallel as one would want, then factoring would only take O(1) speed rather than O(log^3(n)), right?

Aaron

4 Quantum Computers

5 Quantum Computers

6 Quantum Computers

7 Quantum Computers

>	My preferred way to describe quantum computation is by analogy with randomized classical computation.

What do you mean with randomized classical computation?

>	If a computer executes a randomized algorithm, then in a manner of speaking its state is a classical superposition.

What is a randomized algorithm?
Is that an algorithm to calculate random numbers? or is it a Monte Carlo Simulation which uses random numbers?
What do you mean with classical superposition?

>	For some purposes this does afford some computational speedup.

?

>	In quantum computation you replace this classical superposition by a quantum superposition.

Sorry also not clear.

>	It should be believable that this yields yet more speedup than classical superposition does.

Hum.

>	In the most general formalism of this sort, the state of the computer is a density matrix, capturing both classical and quantum superposition. This is in my opinion the best description of quantum computation and quantum probability theory generally.

Is this really the best description possible ?

8 Quantum Computers

9 Quantum Computers

10 Quantum Computers

11 Quantum Computers

Charles DH Williams wrote:

>	In article <3DE7DD7B...@pandora.be>, Nicolaas Vroom wrote:

> >	Suppose this the best classical algorithm:

>

It isn't.

I agree with you. However that is not the issue.
The problem is when you start with a given algorithm with consists of a certain number loops which requires a certain number of steps on a classical computer how can you do that SAME problem in much less steps on a quantum computer.

Both computers considered should be the "same" (i.e. both should be standard from the shelf or both can be special purpose) otherwise any comparison is not scientific.

12 Quantum Computers

Aaron Bergman wrote:

>	In article <3DE7DD7B...@pandora.be>, Nicolaas Vroom wrote:

>>	[Moderator's note: "Shor's algorithm" is the answer to your question. More generally, quantum computers can be more efficient than classical computers because a superposition of states can "perform many loops in parallel" without requiring more hardware (roughly speaking). - KS]

>	Willfully disregarding the disclaimer, is there really any sense in which this is true? It's oft-stated, but from what I know of Shor's algorithm (and what I know is fairly minimal), it works because quantum computers can do FFTs very quickly.

There is a sense in which this quantum parallelism is true. The following example is one part of Shor's algorithm.

Suppose you have a function f:{1,2,3,...,N} -> {1,2,3,...,N} for some sufficiently large N. The only thing which you know about f is that it is periodic, i.e. (roughly speaking) there exist a nuber m so that f(i) = f(i+m) for all i. If you only have a classical computer at your disposal, how often will you have to evaluate f in order to learn m? Right, ~N times.

Using a quantum computer, you can evaluate "all values of f at the same time", by feeding a superposition of all inputs into the function evaluation. However, there is no way to get all results out of the QC, but in this specific case, the only thing you are interested in is the periodicity of the function, while all individual function values are irrelevant. And this is precisely what the QC allows you to do: you can read out this global property of the function, without getting any knowledge about individual function values.

Hope that helps,

Hans

13 Quantum Computers

Robert Tucci wrote:

>	Nicolaas Vroom wrote in message news:<3DE7DD7B...@pandora.be>...

> >	My question is why are both not the same. How do we explain that a quantum computer requires such a relative small number of steps.

>	Basically, when one counts the number of elementary operations (EOs) performed by a classical computer, one is counting scalar multiplications.

What is your definition of scalar multiplications ?

>	With quantum computers, the EOs are *matrix* multiplications.

What is your definition of matrix multiplications ?

>	The matrices being multiplied are not arbitrary--- they must act on one or two qubits only, but each still represents many classical scalar multiplications.

Suppose you have to perform the following program:

1 for i = 2 to 100000
2 for j = 2 to i-1
3 A(j) = A(j) * B(j) / C(j)
4 A(j) = A(j-1) + A(j) + A(j+1)
5 next j
6 next i

Line 3 shows an example of matrix manipulation. The inner loop will benefit from parallelization. This is true for a classical computer and (I expect) for a quantum computer.
For a classical computer this requires more hardware (multi processors) and more memmory. For a quantum computer I do not know what the consequences are.
I expect certain limits are involved.

Line 4 shows an example of matrix manipulation. However this one will NOT benefit from parallelization This is true for a classical computer. I expect the same for quantum computer.

>	Sig:------------------------- A Petition to the American Physical Society for the Creation of a New Acronym (R.I.N.N.O.) http://www.ar-tiste.com/qcomp_onion/rinno.htm

14 Quantum Computers

[Moderator's note: As I noted in another moderator's note, discussion in this thread needs to focus on physics aspects of quantum computation or move to another forum. To a limited extent, posts like this that provide definitions are okay, but, in general, theory of computation is off-topic in SPR. -- KS] In article ,

Nicolaas Vroom wrote:

>>	If a computer executes a randomized algorithm, then in a manner of speaking its state is a classical superposition.

>	What is a randomized algorithm?

...

>	or is it a Monte Carlo Simulation which uses random numbers?

A Monte Carlo simulation is an example of a randomized algorithm. In general a randomized algorithm is one that uses a source of random numbers for some computational purpose. For instance the Miller-Rabin primality test gives statistical evidence as to whether or not a number n is prime by choosing a random residue from 0 to n-1.

>	What do you mean with classical superposition?

In the sense that if you flip a coin, the coin is in a superposition of its heads and tails states until you observe it. Although this is stated using quantum jargon, I am only describing classical probability theory here. In the context of quantum mechanics, a classical superposition is often called a "mixture" and is properly described by a density operator.

In fact there is no strict dichotomy between mixture and quantum superposition, or between classical correlation and quantum entanglement. In both cases the latter is propery understood as a purer form of the former. For instance if you dilute quantum entanglement with noise, it degenerates to classical correlation.

>>	For some purposes this does afford some computational speedup.

>

?

One example is primality tests. The drawback of Miller-Rabin is that it never provides a guarantee that n is prime, only a likelihood. On the bright side, it is faster than any deterministic primality algorithm.

Other algorithms are in the ZPP class. This means that the output is guaranteed to be correct, but the algorithm only probably runs quickly. Here too there are primality algorithms that use a random number generator and that usually run faster than the fastest deterministic algorithm.

15 Quantum Computers

>

In my opinion "parallel computation" is poor terminology for quantum computation. First off it's not clear what it means to allow arbitrary parallel computation. To use Unix terminology, let's say that it means that you can fork processes for free, and that all of the child processes run in parallel but do not communicate. Then the next question is how to reconcile the exponentially many final states of the child processes. One model is the NP model: Children run for polynomial time. If all children say "no", then the parent program outputs "no". If at least one child process says "yes", the parent outputs "yes". Another model is #P: children run for polynomial time and do not communicate; the parent outputs the number of child processes that report "yes".

BQP can be viewed as being contained in a parallel computation class as it is contained in PSPACE and the latter class can be characterized as what you can do in polynomial time if you had access to polynomial in the input many processors. I think the lowest known class classical class containing BQP is AWPP which is a low class in the counting hierarchy which is due to Fortnow and Rogers. The counting hierarchy is basically what you get when you allow yourself the ability to compute exponential sums and products of the results of PTIME computations. That the counting hierarchy is contained in PSPACE can be seen by realizing that to compute say an exponential sum of PTIME computations, we need to keep track of the sum computed so far and then the next term in the sum to be computed, both of which are polynomial size.

Here is my intuition as to why polynomial time quantum computations can be simulated using functions from the counting hierarchy and what makes it hard to simulate a quantum computation in a smaller class like PTIME. To simulate a quantum computation (I am simplifying here a bit) the things we need to be able to compute classically are expressions like: Here x = x1,...,xn in this setup is some number in binary and |vec{x}> is the column vector we get by kronecker producting n vectors of the form [1,0]^T or [0,1]^T together depending on whether xi was 0 or 1. So will be a column vector of length 2^n with all entries 0 except for 1 one. To be able to simulate the computation, it turns out boils down to being able to compute the i,j entry of U efficiently. To calculate the i,j entry of a layer in the case it is a permutation matrix is straightforward. In the case it is a Kronecker product layer one will tend to need to compute a polynomial sized product of complex numbers to get the i,jth entry. To compute the i,j th entry of two layers L and L' one will need to compute Sum^{2^n}_{k=1}l_{ik}l'_{kj}, an exponential sum. So the operations we need to simulate are of the right size to be done in the counting hierarchy. Note I am sweeping under the rug how to handle the complex numbers but this turns out not to be where the hardness is coming from.

The main question is when is it easier to compute the i,jth entry of U? Basically, if the layers of U are matrices in which there are only polynomially many non-zero entries in each row and column and those entries are polynomial time to find, then the whole computation will be in PTIME. What kind of layers satisfy this condition? Well, for instance a permutation matrix will only have one 1 in each row or column. Layers made from reversible classical gates also don't tend to present a problem. Bad layers result from doing things like Kronecker powering more than logarithmically many Hadamard gates together or, for instance, having a layer that did the quantum fourier transform. After creating such a layer it seems hard to avoid brute force computation of an exponential sum to figure out the i,j th entry one would get when we multiply this against another in a typical quantum algorithm

Chris Pollett

16 Quantum Computers

Nicolaas Vroom wrote in message news:<3DEE0367...@pandora.be>...

>	What is your definition of scalar multiplications ? What is your definition of matrix multiplications ?

In linear algebra (vector spaces), one speaks of matrices(linear transformations) and scalars. For example, think of scalars as complex numbers or 1 by 1 matrices.

>	Suppose you have to perform the following program: 1 for i = 2 to 100000 2 for j = 2 to i-1 3 A(j) = A(j) * B(j) / C(j) 4 A(j) = A(j-1) + A(j) + A(j+1) 5 next j 6 next i

17 Quantum Computers

I just noticed this topic, and I'm going to try to answer a few of the questions.

Nicolaas Vroom writes:

> >	Aaron Bergman wrote:

> > >

In article <3DE7DD7B.7A23A1A7@pandora.be>, Nicolaas Vroom wrote:

> >	I did a search with: http://www.google.com/search?q=Shor%27s+Algorithm&hl=en&lr=&ie=UTF8&start=0&sa=N" In my first reply to this posting I already discussed some url's which are mentioned. Unfortunate it is still not clear why you need Shor's Algorithm to factoring a number. For example 15 = 3 * 5.

You don't need Shor's algorithm to factor a number ... you just factored 15 without even using a computer.

And going back to your first posting on this topic, you say (but maybe forgot)

>

At page 51 of Scientific November 2002 is written: "How many computational steps are needed to find the prime factors of a 300-digit number? The best classical algorithm would take about 5*10E24 steps. By taking advantage of innumerable quantum states a quantum factoring algorithm would take only 5*10E10 steps"

So in theory, you can factor a 300-digit number with a classical computer, we just don't have any classical computers fast enough. And 500-digit numbers, without truly signifiant advances in either classical computing power, in algorithms, or in quantum computers, are out of reach.

Nicholaas Vroom also asked

>	My question is why are both [e.g., the classical and quantum number of steps needed not the same. How do we explain that a quantum computer requires such a relative small number of steps.

I'm going to make a fool of myself and answer this by giving a transportation metaphor. To pick an example relatively close to my home, suppose you want to go from Cape May, New Jersey to Lewes, Delaware. Using one of the popular driving directions web sites says it takes 200 miles and four hours. However, you can make the trip in just a little over an hour.

How?

If you look at the map, you find that there's only around 20 miles between these two cities, measured across the mouth of the Delaware bay. And, in fact, there's a regularly scheduled ferry service that runs between them (and which will take your car).

Some people might call this "thinking outside the box." (I would probably call it "taking the ferry.") Notice that you need special hardware to do this (a boat). If you try to do this using only your car (unless you've got a car like James Bond's) you'll drown.

There are computational paths from a number to its factors that only a quantum computer can navigate. Quantum computers can perform steps that might be described in English as "rotate qubit 2 by 90 degrees coherently conditioned on qubit 1 being 0," which translates in mathematics to applying a specific 4x4 matrix on the quantum state space of qubits 1 and 2, and in a specific quantum computater implementation might translate to applying a fixed sequence of properly shaped laser pulses to ions in an ion trap. Try and do this kind of step on a classical computer. A good question here is: how does this kind of step help? For that, you'll have to look more closely at a specific quantum computing algorithm.

18 Quantum Computers

Chris Pollett wrote:

>	BQP can be viewed as being contained in a parallel computation class as it is contained in PSPACE and the latter class can be characterized as what you can do in polynomial time if you had access to polynomial in the input many processors.

When composing my previous posting I had trouble characterizing PSPACE in my mind this way. However, I do remember the result that a sufficiently general tree search with alternating quantifiers is PSPACE-complete - e.g. "generalized chess" is a PSPACE-complete problem. Clearly such a search may be done in polynomial time if you can fork processes for free. Conversely, polynomially many processors can be simulated in polynomial space. So yes, PSPACE is a natural model for fully parallel, polynomial-time computation. Thanks for mentioning this observation.

It is certainly important to know that BQP is contained in PSPACE. However, the proper way to understand that is that BQP is *subsumed* by parallel computation. To say that "quantum computation is a kind of parallel computation", or even "quantum computation allows massive parallelism", leaves many people with the impression that BQP = PSPACE, or at least that BQP is not much smaller than PSPACE. I'm sure you would accept the conjecture that BQP is much smaller than PSPACE (for one thing because it's contained in AWPP, as you say).

My point is that conceptually BQP is a lot like BPP (the most general randomized polynomial-time class), only bigger. At least, that's my conception of it.

You could also point out that BPP is contained in PSPACE. But most people have no trouble understanding that randomized computation is parallel only in a very weak sense. To be sure, it is natural to conjecture that BPP = P and that BQP != P. On the other hand, it is also natural to conjecture that randomization yields a quadratic speedup for some problems over determinism (maybe that's even a theorem). People should appreciate that phenomenon as a warmup to understanding BQP.

19 Quantum Computers

Hi Nicolaas First, let me say that i m just an ordinary student of physics. The people here have a lot more experience than i do.

Anyways, i will give u some pointers.

Quantum Computers do not function like classical computers and so you cannot program them like classical computers. Things like loops, if statements, etc do not directly make sense.

Basically, here a description of a Quantum Computer and how it is supposed to work. The description is a little bit amateurish.

In Quantum mechanics, we talk about ensembles and how things can exists in superposition of states.

For example. Here's the classical analogy

Imagine the boolean gate OR Function

OR(X,Y) = X' * Y + X * Y + X * Y'

Basically, according to classical boolean theory,

OR(X,Y) will be a 1 if X'*Y is 1 , that is to say X=0, Y = 1, or X*Y is a 1, X=1,Y=1, and of if X*Y' is 1, that is X=1, Y=0.

Basically, u also need to notice that X'*Y is orthogonal to X*Y'

that means X'*Y*X*Y' = 0 which is true because X'*X =0 and Y'*Y=0

Now, the above expression can be rewritten as follow

OR = |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|

On a classical computer, at one time X can be either 0 or 1, and so does Y, and so is the output only allowed to be 1 or 0.

Now, on the otherhand, in Quantum mechanics, particles, can exists in superposition of states, that means that,

X can be expressed as a combination of 0 or 1. |X = c_x0 |0 + c_x1|1

Basically, |c_x0|^2 is taken to be the probability of X being a 1. That means that if you measure the state of a particle |X>, you are gaurrented to get 0 or 1, not both at the same time. However, you cannot predict with certainty which state you are going to get. However, the only certainty is probability of getting 0 at X is |c_x0|^2 and probability of getting 1 is |c_x1|^2

Moreover, interestingly, c_x0 can also be complex numbers. After all, the probability is only governed by |c_x0|^2.

So, you may wonder if X what it means to say that X is in superposition of both 1 and 0. There are many interpretations. One interesting one is the many world interpretation.

It says that when a particle is prepared in a superposition of states, like our |X>. the world diverges with X=0 with |c_x0|^2 and X=1 with |c_x1|^2.

where |c_x0|^2 + |c_x1|^2 = 1

And we can also express Y as follows |Y> = c_y0 |0> + c_y1|1>

Now, if you increase the number of input variables, for example say n = 128, you have in fact, prepared a system with 2^128 states. However, if you try to measure the state of |X_1,X_2,...X_n>, you will only get one of all possible 2^128 states. Because of this dynamics, a Quantum computer can try 2^128 states in parallel at the same time.

Now, our expression is still given by

OR(X,Y) = X' * Y + X * Y + X * Y'

However, you need to understand since X and Y are no longer binary, OR(X,Y) is not gaureented to be 1 or 0. Rather OR(X,Y) has a probability of being 1 or 0.

Upto now, you will be inclined to ask, that well, how it is useful. After all, you are preparing a system in 2^128 states. And you get only one answer. So, you may ask, how you can get the answer you are looking.

Now, Quantum Mechanics is not so simple, as the worlds diverging. In fact, the worlds can interfere and cancel themselves out.

|c_x0|^2 is the probability of getting x=0,however, c_x0 can also be a complex number. So, it has phase. c_x0 = p_x0 exp(i theta_x0).

This makes matters a lot of complicated.

The innocent looking presence of phase allows the different worlds to interfere.

Let's go back to our expression

OR = |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|

Our OR gate, can be seen as an evolution device. In Quantum Mechanics,the word used to denote an OR like device is 'operator'. Basically, the application of the OR gate to the quantum sytem input system |X,Y> , evolves it from that state to the state at the output.

After all, this is even classical gates do. Given an input state, they take it to the

output state.

Moreover, just as our classical device, |k> where k' != k and i' != i and j' != j. Where a != b means a is not equal to b.

In Quantum mechanics, there is a requirment for probability conservation

Basically, it goes something like this

sum_i |c_xi|^2 = 1

This is true of any probability theory. The sum of probabilities is always 1. After all, this is an axiom of probability theory.

There is another equivalent statement called the Unitary requirement that has the same effect as probability conservation.

Our expression OR = |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|

[Thanks to Kevin Scaledeferri, for pointing out the correct form of the expression]

Suppose we rewrite our OR expression as

OR = a[01->1] |1><0,1| + a[10->1] |1><1,0| + a[11->1] |1><1,1| + a[00->0] |0><0,0|

Comparing the 2 expression above, we can decipher that

a[ij->k] = 1.

However sum_[ij->k] |a_[ij->k]|^2 /= 1. And so it does not converse probability.

However, for example,

OR = (1/sqrt(4)) ( |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|)

does

a_[ij->k] = 1/2

sum_i |a_[ij->k]|^2 = 1

Now, suppose multiply |X> and |Y>, we get |X>|Y> = c_x0 c_y0 |X=0>|Y=0> + c_x1 c_y0 |X=1>|Y=0> + c_x0c_y1 |X=0>|Y=1> + c_y1 c_x1|X=1>|Y=1>

othewise written as,

|X,Y> = c_x0 c_y0 |0,0> + c_x1 c_y0 |1,0> + c_x0c_y1|0,1> + c_y1 c_x1 |1,1>

Where |c_x0 c_y0|^2 is the probability of getting a X=0,Y=0. It is also consitent wth |c_x0 c_y0|^2 = |c_x0|^2|c_y0|^2. This expression means that p(X = 0 and Y=0) = p(X=0) p(Y=0).

This is a natural expression for the probability of independent events.

Now, back to our OR operator

Now, if i apply the OR operator to our input state |X,Y>

OR|X,Y> = (1/sqrt(4)) ( |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|)

c_x0 c_y0 |0,0> + c_x1 c_y0 |1,0> + c_x0c_y1|0,1> + c_y1 c_x1 |1,1>

the resulting expression is

= (1/2) |1> ( c_x1 c_y0 + c_x0c_y1 + c_y1 c_x1 ) + (1/2) |0> ( c_x0 c_y0)

So, the probability of getting a 1, is

|<1|OR|X,Y>|^2 = (1/4) | c_x1 c_y0 + c_x0c_y1 + c_y1 c_x1|^2

= 1/4 |p_x1p_y1 exp(i (theta_x1 + theta_y1) ) + p_x1p_y0 exp( i(theta_x1 + theta_y0)) + p_x0 p_y1 exp( i(theta_x0 + theta_y1))|^2

In the above expression, it is important to notice that the phases interfere with each other and cancel each other out. This is what creates all the difference in the world. The phases are not innocuous as we had thought them to be.

So, not only do the worlds seperate at each instant, they also interfere with each other. So, voila, parallel computing.

---- Revisible Computing and answers to NP-completeness

A example of factorization ----

Basically, suppose we take a (2n)-bit multiplier with 2 n-bit multiplicand with (2n)-bit output. Now, suppose be interested to know a few things. We take the output of the (2n-bit) multiplier and put a big AND gate at end. The output of this gate is true, if in fact, an input combination of mutiplicand produces the the number to be factored at the output. Suppose We are interested in factoring [O_0,O_1,O_2...,O_n] = [0,1,1,0...,1] . Let's call this number N . Our AND gate basically, is O_0'*O_1*O_2*O_0'...*O_n

In normal binary computers, certain operations are not reversible.

For example, back to our OR gate.

Suppose X=0,Y=1. The output of the OR gate is 1. However, based on the output, we cannot tell if the input was X=0,Y=1, or X=1,Y=1 or X=1,Y=0. So, you can even say that information is lost from inputs to the outputs. Suppose, i have a random binary generator at the input. Based on the output of a classical gate, mostly impossible to tell what the inputs of the circuit were.

Now, the idea of Quantum Computing, leads to reversible computing. [I m not an expert on this topic either. I am not sure if Quantum Computing requires reservsible computing]. However, a Quantum equivalent of 2-bit AND Gate, has 4 not 3 connections coming in and going out.

a Quantum 2-qubit AND gate needs to have 2 inputs, one output, and one revisibility channel.

So, now, suppose, we have the quantum equivalent of this classical multiplier, because of reversibility of we can propogate the 1 from the output of our AND gate, in our multiplier, and trace them back to the input combinations that generate the 1 at the output. Notably, these combinations are also factors or our number N.

Shor's algorithm is different. But, hopefully, this helps.

-suresh

20 Quantum Computers

>	Nicolaas Vroom writes:

> >	Unfortunate it is still not clear why you need Shor's Algorithm to factoring a number. For example 15 = 3 * 5.

>	You don't need Shor's algorithm to factor a number ... you just factored 15 without even using a computer.

After studying Shor's algorithm and quantum computers (I'am still in that process) three items are still not clear to me:
1. Why does one need FFT in order to factor a number
2. Why are quantum computers soo much faster
3. Shor's algorithm does not always work.
4. Why not implementing the whole algorithm on a quantum computer.

21 Quantum Computers

Nicolaas Vroom wrote:

>	It should be possible to simulate any program that runs on a quantum computer on a classical computer.

Yes, this is true. However, the simulation is not efficient.

There are many models of computation which are equivalent, meaning that they can simulate each other. However, computational equivalence doesn't mean the complexity is the same. Frequently the simulation involves an exponential increase in the time or space requirements.

22 Quantum Computers

Nicolaas Vroom wrote:

>	4. IMO the best one is: http://everest.uwyo.edu/~moorhous/quantum/talk2.pdf This document explains in detail: Example factor n = 55

After studying this document IMO Shor's algorithm 1. works for the following factors: 5 * 11 =55 3*17, 3*19
5*7, 5*11, 5*13, 5*17,
7*13, 7*17, 7*29
17*31 Because the number of numbers (a mod x) in step 2 until you find the number 1 is odd.
y is the number in the middle. After finding y you can proceed to step 6.
For example for 5 * 11 = 55 those numbers are:
13,4,52,16,43,9,7,36,28,*34*,2,26,8,49,32,31,18,14,17 y=34
For example for 3 * 17 = 51 those numbers are: 13, *16*, 4
y=16

2. does not work for the following factors:
5*29
Because the number of numbers (a mod x) in step 2 until you find the number 1 is even.
For example for 5 * 29 = 145 those numbers are: 16, 111, 36, 141, 81, 136

3. does not work for the following factors:
3*5, 3*11, 3*13
5*19, 5*23
7*11, 7*19, 7* 23 19*31 Because there is no 1
For example for 3*5=15 those numbers are: 9,6,9,6,9,6,9,6,
For example for 3*11=33 those numbers are: 12,12,12,12,12
For example for 7*11=77 those numbers are: 14,42,49,70,56

23 Quantum Computers

(performing a quantum elementary operation) = multiplying quantum state (given by a 2^NB long, column vector of complex numbers) by a 2^NB times 2^NB elementary matrix

This suggests that sometimes one elementary op of a quantum computer accomplishes on the order of 2^NB elementary classical operations

An elementary matrix, by definition, can only *change* the state of one or two qubits, not more. The rest of the qubits are acted upon without changing them. This acting upon certain qubits of the qubit array without changing them (while at the same time changing other qubits in the array), "is key" for vector spaces and quantum physics, but not as key in classical physics.

Sig:-------------------------

24 Quantum Computers

Nicolaas Vroom asks:

>	After studying Shor's algorithm and quantum computers (I'am still in that process) three items are still not clear to me: 1. Why does one need FFT in order to factor a number

It's the only way we know of to factor a number fast on a quantum computer. The two-sentence intution: We factor by finding periodicity. FFT's are very good at finding periodicity.

>	2. Why are quantum computers soo much faster

It's not that they're faster ... it's that they can do kinds of subroutines and algorithms that classical computers can't, so certain problems will take many fewer steps. If you run the SAME algorithm on a classical computer and a quantum computer, the quantum computer will probably be slower because in building a quantum computer, you have to worry about reversibility and coherence, which are likely going to force you to operate more slowly than a classical computer.

>	3. Shor's algorithm does not always work.

The fastest classical algorithms for factoring are randomized, as well. If you run Shor's algorithm enough times, you will almost certainly find the factors. This is exactly the same situation as the quadratic or number field sieves. If you want an algorithm which deterministically factors, you have to use a substantially slower one.

>	4. Why not implementing the whole algorithm on a quantum computer.

You could. But because quantum computers are going to be so much more expensive than classical computers, this is not goint to be a good idea in practice.

I said:

> >	Try and do this kind of step on a classical computer. A good question here is: how does this kind of step help?

>	Exactly Why do you need this. Does it work in practice. How far are we in the laboratory ?

You need this type of step to compute a quantum Fourier transform. The quantum computing algorithm has factored 15 (there's some debate about whether this was a true quantum computation or not, because it was done using NMR, but I suspect that 15 will be factored in the next few years by a less controversial technology). This took 6 qubits and a few hundred steps. To factor a 300-digit number, you probably need several thousand qubits (depending on how much error correction is required) and several billion steps.

About trial division (which Nicholas Vroom suggested as a factoring algorithm), I said:

> >	The computer science side of me absolutely insists on saying something here. This is nowhere near the best algorithm,

>	There are two issues involved: 1. a) Start from a given algorithm, b) implement that algorithm on both a classical computer and a quantum computer c) calculate solution time i.e. speed 2. Find the fastest algorithm which solves a given problem for both a classical computer and a quantum computer.

>	The pseudo-code addresses the first issue. i.e. I want to understand if and how quantum computers are faster using the same algorithm (program)

Finally, you have expressed this question in a way that I can understand it. No, quantum computers are not faster using the same algorithm. That's why you need all these funny quantum coherent steps and the FFT.

>	Conclusion: Speed up gained by sieve algorithm is 126 orders. Speed up gained by quantum algorithm is 140 orders. How do you explain that quantum algorithm is better than sieve algorithm ?

How do you explain why the sieve algorithm so much better than trial division? Why trial division is better than guessing an answer and then checking it (this will also, theoretically, eventually factor). Why is the number field sieve better than the quadratic sieve?

Determining how many steps a given algorithm uses is one of the central concerns of theoretical computer science, and in the case of the number field sieve, involves some fairly difficult mathematics. I discovered the quantum factoring algorithm and showed that it was polynomial time. Nobody has figured out how to factor in polynomial time on a classical computer.

>	Is this more than only a prediction ?

Since nobody has actually factored a generic 300-digit number, using either a classical or quantum computer, how could this be more than just a prediction?

If you mean, can you write down an algorithm which is guaranteed with high probability to factor a 300-digit number, with a specified number of steps, assuming that somebody has a quantum computer to run it on. yes.

>	It is IMO easy possible that factoring a number on a quantum computer plus classical computer combination is slower than performing the same factoring on a classical computer which uses the sieve algorithm.

Why?

Do you not believe that quantum computers will ever be built? (a reasonable point of view).

Do you not believe that quantum mechanics is correct? (a view shared by a number of otherwise reasonable people, but one which I think requires ignoring a great deal of evidence).

Do you not believe the prediction of the number of steps taken by a quantum computer using the factoring algorithm is correct, assuming that quantum computers can be built? (I don't believe I've encountered somebody holding this view before).

Do you believe that conventional computers will be 14 orders of magnitude faster than quantum computers?
(Very optimistic prediction of technology for conventional computers, even if quantum computers have the ridiculously slow millisecond clock times of NMR technology.)

Do you believe that the number field sieve algorithm is orders of magnitude faster than the observed and theoretically predicted running times for it?
(The running times for the number field sieve have not been rigorously proved mathematically, but believing this would be ridiculously optimistic.)

I hope this helps,

Peter Shor

25 Quantum Computers

Nicolaas Vroom wrote:

>

1. Quantum Computing, Shor's Algorithm, and Parallelism Arun, Bhalla, Kenneth Eguro, Matthew Hayward http://alumni.imsa.edu/~matth/quant/433/shor-par/ Shor's algorithm is discussed at: http://alumni.imsa.edu/~matth/quant/433/shor-par/node12.html The most details are at: http://alumni.imsa.edu/~matth/quant/433/shor-par/node15.html This page claims that in order "for factoring a given integer n" you need (see step 1-4) a classical computer. I found that very strange.

Well, you don't _need_ to do those steps on a classical computer, but they are efficient on a classical computer. Given that the clock speeds of classical computers are massively higher that quantum computers for the forseeable future, it makes sense to take such a hybrid approach.

>	Starting with step 5 you need a quantum computer In step s discrete Fourier transform is computed. Why do you need that in order "for factoring a given integer n" ?

You don't need a Fourier transform to factor an integer. There are many algorithms for factorization that don't use this technique at all. However, the key in this approach is the periodicity of x^a mod n, and you should be able to see that a Fourier transform is handy if you want to pick out periods of a functions.

>	http://alumni.imsa.edu/~matth/quant/433/shor-par/node16.html claims: "In general Shor's algorithm simulation seems a good candidate for parallelization." Why the word simulation ?

Simulation means modeling one type of machine on another. In this case, we are talking about modeling the execution of a quantum computer (quantum register machine) on a classical computer (classical register machine).

>	Why the word seems ? Does this imply that we are not sure ?

The don't prove this to be true at any point that I can see.

>	After studying the above documents (I'am still in that process) I have the following remarks. 1. Shor's Algorithm allows you (As far as I currently understand) to perform factoring of an integer. 2. In order to do that you need both a classical computer and a quantum computer.

No, you could do it all on a quantum computer (in theory)

>	3. It is not clear to me if you can do this whole calculation solely on a classical computer.

Yes, but it will be slower

>	4. It is not clear to me what the advantages are by using a quantum computer.

Speed

>	5. Assuming remark 1 is correct and assuming that using a classical computer and a quantum computer both together, is the best way to implement shor's algorithm than I'am still not convinced that quantum computers in general are faster (and eventualy will replace classical computers)

Good! No one knows that practical QCs are possible nor that the requirements for general error correction won't outweigh the theoretical speedup under perfect conditions.

>	6. Shor's Algorithm smells like a Monte Carlo simulation. As part of the algorithm you have to observe register 2 and to measure register 1 (See url in remark 4) It is not clear to me if you only have to do this once.

No, you might have to do it more than once. However, the speedup is great enough that the possibility of having to repeat the calculation a couple times is insignificant.

>	7. Assuming that you have to do this more often what is the chance that you never find the right answer specific with large numbers ?

That you never find the right answer? 0 (ignoring the issues of error correction and such, which we are generally ignoring already)

What you really want to know is, what is the chance that you don't find the answer in an exponential number of trials. Unfortunately, I don't know the answer off-hand, but it should be exponentially small.

>	8. It is interesting to study what happens if the number that you want to factor (using Shor's algorithm) is a prime number.

Maybe, although there are efficient algorithms for determining primality, so there isn't much point in using Shor's algorithm.

26 Quantum Computers

27 Quantum Computers

To understand if FFT's work on a Quantum Computer (QC) I have a number of questions.

28 Quantum Computers

29 Quantum Computers

Nicolaas Vroom wrote:

>

If you study https://www.nicvroom.be/shor.htm and the simulation program than you will see that IMO you can factorize a number with (part of) Shor's Algorithm only on a standard PC without FFT's. IMO Shor's Algorithm requires more steps/calculations than a classical factorization algorithm (For example 29*31 requires 420 steps versus 30 steps)

That's nice, but it's really beside the point. What does your simulation say when instead of the factors being 29 and 31, they are 29 and 31 digits long? Or 290 and 310 digits?

Because your later comments in the post lead me to believe that you are confused on this point, let me explain that when computer scientists talk about the "speed" of an algorithm, they usually mean the asymptotic scaling of the algorithm for large inputs.

However, when

>	Peter Shor wrote: No, quantum computers are not faster using the same algorithm.

He was actually talking about the fact that the clock speeds of quantum computers are much lower than classical computers, for the forseeable future.

When I said:

>

>> >	3. It is not clear to me if you can do this whole calculation solely on a classical computer.

>>	Yes, but it will be slower

I was referring to the fact that a classical computer can't truly execute the same algorithm as a quantum computer. When a classical computer simulates Shor's algorithm, it is running a different algorithm which scales much worse.

This is a little subtle, since people are often a little sloppy with the terminology. However, to really talk about the complexity of an algorithm, you need to know the machine architecture well enough to know what the fundamental operations are.

30 Quantum Computers

"Kevin A. Scaldeferri" wrote:

>	In article <3E00886B...@pandora.be>, Nicolaas Vroom wrote:

> >	If you study https://www.nicvroom.be/shor.htm and the simulation program

> >	than you will see etc.

> >	(For example 29*31 requires 420 steps versus 30 steps)

>	That's nice, but it's really beside the point.

IMO this is a very important statement Shor's Algorithm consists of three parts: 1. Pre Processing. 2. FFT 3. Post Processing.
The Pre and Post Processing part are performed on a classical comp. The FFT part is performed on a quantum (post) comp.
IMO in order to do factorization you do not need the FFT part.

31 Quantum Computers

... long sections snipped ...

>	A different question is how many steps are involved and how long does it take to do a full factorization with a classical algorithm on a Quantum Computer (without FFT.) without any optimization (sieve) i.e. are this 10^150 calculations for two 150 digit numbers?

Saying that the quadratic (or number field) sieve is an optimized version of trial division is kind of like saying that an automobile is an optimized version of a donkey cart. They work using completely different principles; if you were programming them, the only code you could reuse is the code for multiplication and division of large numbers. I would recommend reading a good explanation of the quadratic sieve. Unfortunately, the only one I know of offhand (Brain Hayes' article "The magic words are squeamish ossifrage") is not available online.

Peter Shor

32 Quantum Computers

33 Quantum Computers

>	Nicolaas Vroom wrote:

> >	Step 2 involves modular exponentation i.e. the calculation of x^a mod n with a going from 0 to 8191 This are 8192 values, calculations or 8192 steps !!! Those steps are required to initialize FFT on the quantum comp. This number of preprocessing steps (=q) is gargantuan and IMO not necessary.

>	Step 2 isn't preprocessing in the quantum factoring algorithm; it's intrinsically part of the quantum piece of the algorithm. If you want to simulate the quantum algorithm on a classical computer, you do indeed need these 8192 calculations.

I doubt that. If you test if x^a mod n = 1 (for a from 0 to 8191) you can stop. Than you know the periodicity.

13^20 mod 55 = 1

34 Quantum Computers

35 Quantum Computers

I'm not going to say anything is *impossible*, but I would say *highly* implausible.

You should note that in Quantum theory, the "number of states in a superposition" is not a physical quantity. It depends strongly on your choice of a basis. Looked at one way, you might have a superposition of a very large number of states, but just by *thinking* about it differently, it becomes a single state with no superposition involved at all.

The "Quantum" answer is no, it isn't possible.

>	we are kind of gaining massively parallel execution without paying anything for that, right? It's as if the nature was "storing" huge, in fact unbounded in principle, amounts of "data" for us.

Maybe "kind of". Quantum and clasical information are sort of like Dollars and Soviet Rubles used to be. Dolars were obviously better than Rubles, but if you wanted to covert Dollars to Rubles (or buy something priced in Rubles) you had to accept the official 1 to 1 exchange rate. The universe has no black market.

It *looks* like nature *must* be storing lots of data, but when you try to retrieve that data, you only get one classical bit per qbit. (Similarly, by violating Bell's inequality, it *looks* like nature *must* be transmiting information instantainiously, but if *you* want to send some, you can't.)

>	Could the theory of quantum mechanics be changed so that superpositions with very very large number of states in them would be outlawed, and the theory would still remain logically coherent? Perhaps by positing that such "large" superpositions would collapse as if observed, or in some other manner?

I doubt it, and I'm pretty sure such a theory wouldn't look much like quantum mechanics. Ordinary quantum effects typically do involve superpositions of very large (if not infinite) numbers of states.

For instance, light can be focused to a fine point, but can also be prepared in a state with a very small uncertianty in momentum. In quantum mechanics, position states can be described as infinite superpositions of momentum states, and vice versa.

For what you are suggesting to happen, one type of states (lets assume for concreteness that it is position states) would have to be the "real" states and the other (momentum) the "superpositions". If there were a bound on the number of "real" states in a superposition, there would be a limit to how precicely the "superpositions" could be measured. In our example that would be a limit to how coherent a laser could be.

I don't know what the experimental limit on such an effect would be, but I would guess that it is *very* tight. Probabally tight enough that it wouldn't bother any practical quantum computer (there *are* lots of things that *do* make a quantum computer hard to build).

Ralph Hartley

36 Quantum Computers

"Ralph Hartley" wrote

>	It *looks* like nature *must* be storing lots of data, but when you try to retrieve that data, you only get one classical bit per qbit.

This has always made me sceptical about whether quantum computers could ever work in theory, even if the practical problems could be over come (which I'm sure they will, eventually).

This point often seems overlooked by proponents of quantum computers. I have never seen a cogent explanation of how the result is read out of a quantum computer, in a fashion that is superior to a classical computer.

Bucksbaum's "Library of Congress in an electron" claim fails at this reading out stage; this major difficulty is only obscured because his experiments are operating on millions of identically prepared electrons. By operating on such a large number of electrons or atoms Bucksbaum' is able to exploit the million-fold parallelism present and thereby extract information to digitally reconstruct the electrons' wavefunctions. In this experiment, information recovery is limited 3 bits per electron - each electron in his setup can occupy one of 8 levels. The more atoms used the more information they can recover.

In effect they haven't got a new-fangled quantum computer but an old-fashioned parallel-processing computer.

Is this a generic problem with all quantum computers?

Cheers, Michael C Price

37 Quantum Computers

Anatoly Vorobey wrote:

>	In article , Peter Shor wrote:

> >	Some poor soul not cited by Anatoly Vorobey wrote:

>

> >>	It is IMO easy possible that factoring a number on a quantum computer plus classical computer combination is slower than performing the same factoring on a classical computer which uses the sieve algorithm.

>

I wrote that in message 7 in this thread.

[Moderator's note: "message 7" is not anything well-defined -- KS]

But unfortunate after studying documents related to quantum computers my understanding of how quantum computers operate is becoming less.

38 Quantum Computers

39 Quantum Computers

Nicolaas Vroom wrote:

>	I have also improved my similation program of the 6 steps outlined in document 1. https://www.nicvroom.be/progrm19.htm Is my simmulation program correct?

40 Quantum Computers

Nicolaas Vroom wrote:

>

My interpretation of the FFT values in step 5 is that we only have a 16/16384=1/1024 chance of finding the value 1024 and a 1023/1024 chance of finding the value 0. What is the correct interpretation? Is my simmulation program correct? Nick http://www.nicvroom.be/ Question 23 Discusses Shor's Algorithm

41 Quantum Computers

Nicolaas Vroom wrote:

>	What is the correct interpretation? Is my simmulation program correct?

With my simulation program you can factorize 8383 First it tells you that x=28 and q=268435456.
You measure register 2 on your QC You can enter nothing than it selects something random But you can also select 1 for the next step.

Than you measure register 1 on your QC You again can enter nothing than the QC selects something random But you can also select for example 65472 or (205123972)
As a result of Step 6 on your PC you perform Continued Fraction Convergent of 65472

 0 a = 0      p =  65472 / 268435456
 1 a = 4100   p =  256 / 65472    Convergent  1 / 4100
 2 a = 255    p =  192 / 256      Convergent  255 / 1045501
 3 a = 1      p =  64 / 192       Convergent  256 / 1049601
 4 a = 3      p =  0 / 64         Convergent  1023 / 4194304

The next step is to calculate y = 28^2050 mod 8383 The result is 3736
But how do you do that "fast" in "one step" ? On my pc I do that in a do loop of 2050 calculations but that is a slow methode.

In order to calculate 28^2050 you need a tremendous powerfull PC which huge registers.

Remember this is only a simple example for really large numbers of 100 digits this becomes impossible to handle except if you do it in a loop but that makes shor's algorithm very slow.

If some one thinks that you can perform this single calculation on a Quantum Computer than please give me the details how this works internally.

Finally If you have y = 3736 Than you have to calculate GCD(3737,8383) and GCD(3735,8383) which will give you the final answer 83 and 101 But that is easy and gives no problem on a PC

>	Nick https://www.nicvroom.be/ Question 23 Discusses Shor's Algorithm